1. Technical Field
The field of invention relates to databases. In particular, the field of invention relates to reorganizing a table according to multiple sparse indexes.
2. Description of the Related Art
Databases use tables to organize information. Each table consists of a number of rows, each of which corresponds to a single database record. Keys are used to organize the database. Each database table has one or more columns designated as the primary key. The value of this key is unique for each record in the database. For example, assume a table exists that contains personnel information on every employee in an organization. An example of a primary key in this scenario would be an employee serial number unique to each employee.
A database index is a data structure that improves the speed of operations in a table. Indexes can be created using one or more columns, providing the basis for both rapid random lookups and efficient ordering of access to records. The disk space required to store the index is typically less than the storage of the table (since indexes usually contain only the key-fields according to which the table is to be arranged, and excludes all the other details of the table). Thus, indexes can be stored in memory in instances where the entire table might not fit.
Database tables are traditionally organized physically on a storage medium (such as a hard disk) according to some index (e.g., a primary key such as employee serial number). In most instances, rows within the database table are processed on a key ordered basis. Thus, physically storing database tables on the disk in keyword order minimizes I/O time, since multiple rows can be brought into memory with each I/O operation.
Structured Query Language (SQL) sparse indexes are a newer technology that is gaining popularity. A sparse index is an index with a key and pointers to rows in a database table for a subset of data in the table. Every key in the index is associated via pointers with a row in the database table. However, not every row in the table may be pointed to by a key in the index. Application designers have begun to create multiple sparse SQL indexes to tune particular application queries. For many highly tuned applications, hundreds or even thousands of sparse indexes may be created to match many of the application queries.
Currently, there is no way to physically reorganize a table according to multiple sparse indexes. Thus, as multiple sparse index use becomes more common in some environments, performance may be suboptimal due to high randomness of the I/O operations. For example, if a particular index selects n rows, the n rows may be spread over up to n blocks of data on disk causing up to n IOs when they are read into memory.